package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：求二叉树的最小深度
 * @Author Gavin
 * @date 2021.12.19 21:03
 */
public class tree_3 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);

        TreeNode c_1=new TreeNode(2);
        TreeNode c_2=new TreeNode(4);
        TreeNode c_3=new TreeNode(5);
        TreeNode c_4=new TreeNode(6);
        root.left=c_1;
        root.right=c_2;
        c_1.left=c_3;
        c_3.right=c_4;

        System.out.println(solution_1(root));

    }
    /**
     * 第一种方法：
     * 采用递归的方法
     */
    //Time:O(n) Space:O(n)
    public static int solution_1(TreeNode root){
        //确定递归的终止条件

        //如果根节点为null返回0
        if(root==null)return 0;
        //如果是根节点的左子树和右子树都为null，说明就是叶子节点，返回1
        if(root.left==null&&root.right==null)return 1;
        //如果根节点的左子树为null，就递归计算右节点
        //注意这里和求最大深度的区别，如果左子数为null的时候并不能认为最小深度为0，
        // 最小深度的概念是根节点到叶子节点（叶子节点左右子树都要为null）的最短距离
        if(root.left==null)return solution_1(root.right)+1;
        //如果根节点的右子树为null，就递归计算左子树深度
        if(root.right==null)return solution_1(root.left)+1;
        //如果左右子树都不为空
        return Math.min(solution_1(root.left),solution_1(root.right))+1;
    }
    /**
     * 第二种方法：
     * 使用一个队列来处理，按照树的层级来处理，每一层的每个节点依次判断
     * 如果判断到该层的某个节点的左右子树都为null了说明深度就是到这一层了，
     * 否正就把这层每个节点的左右子树继续入队进行循环
     */
    //Time:O(n) Space:O(n)
    public static int solution_2(TreeNode root){
        if(root==null)return 0;
        Queue<TreeNode> q=new LinkedList<>();
        //首先把根节点入队
        q.add(root);
        int depth=1;
        while (!q.isEmpty()){
            int size=q.size();
            //循环每一层的节点
            for (int i = 0; i < size; i++) {
                TreeNode preRoot=q.poll();
                if(preRoot.left==null&&preRoot.right==null)return depth;
                if(preRoot.left!=null)q.add(preRoot.left);
                if(preRoot.right!=null)q.add(preRoot.right);
            }
            ++depth;
        }
        return -1;
    }
}
